1556B - Take Your Places - CodeForces Solution

/*                                   PREFER DARK MODE BECAUSE LIGHT  ATTRACTS BUGS                                  */
#include<bits/stdc++.h>

using namespace std;



#define fastio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define MOD 1000000007
#define MOD1 998244353
#define INF 1e18
#define nline "\n"
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define ff first
#define ss second
#define PI 3.141592653589793238462
#define set_bits __builtin_popcountll
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()

typedef long long ll;
typedef unsigned long long ull;
typedef long double lld;
// typedef tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update > pbds; // find_by_order, order_of_key

#ifndef ONLINE_JUDGE
#define debug(x) cerr << #x <<" "; _print(x); cerr << endl;
#else
#define debug(x)
#endif

void _print(ll t) {cerr << t;}
void _print(int t) {cerr << t;}
void _print(string t) {cerr << t;}
void _print(char t) {cerr << t;}
void _print(lld t) {cerr << t;}
void _print(double t) {cerr << t;}
void _print(ull t) {cerr << t;}

template <class T, class V> void _print(pair <T, V> p);
template <class T> void _print(vector <T> v);
template <class T> void _print(set <T> v);
template <class T, class V> void _print(map <T, V> v);
template <class T> void _print(multiset <T> v);
template <class T, class V> void _print(pair <T, V> p) {cerr << "{"; _print(p.ff); cerr << ","; _print(p.ss); cerr << "}";}
template <class T> void _print(vector <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(set <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(multiset <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void _print(map <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}

//


void solve() {
	ll n;
	cin >> n;
	vector<ll> v(n);
	ll l, m;
	for (ll i = 0; i < n; i++)
	{
		cin >> v[i];
	}
	ll cnte = 0, cnto = 0;
	for (ll i = 0; i < n; i++)
	{
		if (v[i] % 2 == 0)
		{
			cnte++;
			v[i] = 0;
		}
		else {
			cnto++;
			v[i] = 1;
		}
	}


	if (cnto > cnte)
	{
		if ((cnte + 1) != cnto)
		{
			cout << -1 << endl;
			return;
		}
	}
	else if (cnte > cnto)
	{
		if ((cnto + 1 ) != cnte)
		{
			cout << -1 << endl;
			return;
		}
	}
	debug(v)
	if (cnto > cnte)
	{
		vector<ll> temp;

		for (ll i = 0; i < n; i++)
		{
			if (i % 2 == 0)
				temp.push_back(1);
			else {
				temp.pb(0);
			}
		}
		debug(temp);
		vector<ll> loc;
		for (ll i = 0; i < n; i++)
		{
			if (v[i] == 1)
			{
				loc.pb(i);
			}
		}
		debug(loc)

		ll k = 0;
		ll ans = 0;
		for (ll i = 0; i < n; i++)
		{
			if (temp[i] == 1)
			{
				ans = ans + abs(i - loc[k]);
				k++;
			}
		}
		debug(ans);
		cout << ans << endl;
	}
	else if (cnte > cnto)
	{
		vector<ll> temp;

		for (ll i = 0; i < n; i++)
		{
			if (i % 2 == 0)
				temp.push_back(0);
			else {
				temp.pb(1);
			}
		}
		debug(temp);
		vector<ll> loc;
		for (ll i = 0; i < n; i++)
		{
			if (v[i] == 1)
			{
				loc.pb(i);
			}
		}
		debug(loc)

		ll k = 0;
		ll ans = 0;
		for (ll i = 0; i < n; i++)
		{
			if (temp[i] == 1)
			{
				ans = ans + abs(i - loc[k]);
				k++;
			}
		}
		debug(ans)
		cout << ans << endl;
	}
	else {
		vector<ll> temp1;
		vector<ll> temp2;

		for (ll i = 0; i < n; i++)
		{
			if (i % 2 == 0)
				temp1.push_back(0);
			else {
				temp1.pb(1);
			}
		}
		debug(temp1);

		vector<ll> loc;
		for (ll i = 0; i < n; i++)
		{
			if (v[i] == 1)
			{
				loc.pb(i);
			}
		}
		debug(loc)

		for (ll i = 0; i < n; i++)
		{
			if (i % 2 == 0)
				temp2.push_back(1);
			else {
				temp2.pb(0);
			}
		}
		debug(temp2);

		ll k = 0;
		ll ans1 = 0;
		for (ll i = 0; i < n; i++)
		{
			if (temp1[i] == 1)
			{
				ans1 = ans1 + abs(i - loc[k]);
				k++;
			}
		}
		debug(ans1)

		k = 0;
		ll ans2 = 0;
		for (ll i = 0; i < n; i++)
		{
			if (temp2[i] == 1)
			{
				ans2 = ans2 + abs(i - loc[k]);
				k++;
			}
		}
		debug(ans2)
		cout << min(ans1, ans2) << endl;
	}
	// if (cnto >= cnte)
	// {
	// 	for (ll i = 0; i < n; i++)
	// 	{
	// 		if (v[i] % 2 != 0 && ((i + cnt) % 2 == 0))
	// 		{
	// 			temp1.pb(i + cnt);
	// 			cnt++;
	// 			debug(i)
	// 			debug(temp1)
	// 			debug(cnt)
	// 		}
	// 		else {

	// 			ans = ans + i - temp1[0];
	// 			temp1.erase(temp1.begin());
	// 			debug(i)
	// 			debug(ans)
	// 			debug(temp1)
	// 		}
	// 	}
	// }
	// debug(temp1)
	// debug(ans)

}


int main() {
#ifndef ONLINE_JUDGE
	freopen("Input.txt", "r", stdin);
	freopen("Output.txt", "w", stdout);
	freopen("Error.txt", "w", stderr);
#endif
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	ll t;
	cin >> t;
	while (t--)
		solve();

}